/**
 * 
 */
package dp;

import java.util.Arrays;

/**
 * 这是昨天做的一道题。其实一看就是一道简单的DP题，但是有很多网友说可以用trie来做，
 * 因此就实现了一下，感觉trie比DP的代码要复杂很多。从时间复杂度来说，DP是O(m*n), 
 * 而trie是O(m^2+n^2), 如果m和n差不多的话，一个复杂度。如果一长一短的话，DP有优势。
 * 空间复杂度，DP可以优化到min(m,n), 比trie要好很多。因此对于面试来说，DP貌似是最好的solution。
 * 
 * @author xyyi
 * @version 2013/02/27
 * @since   2013/02/27
 *
 */
public class LongestCommonConsecutiveSequence {

	/**
	 * 
	 */
	public LongestCommonConsecutiveSequence() {
		// TODO Auto-generated constructor stub
	}

	// Space O(mn) time O(mn)
	public int lccsDP(char[] arr1, char[] arr2) {

		int[][] dp = new int[arr1.length + 1][arr2.length + 1];

		int max = 0;
		for (int x = 0, size1 = arr1.length; x < size1; ++x) {
			for (int y = 0, size2 = arr2.length; y < size2; ++y) {
				if (arr1[x] == arr2[y]) {
					dp[x + 1][y + 1] = dp[x][y] + 1;
				} else {
					dp[x + 1][y + 1] = 0;
				}
				max = max < dp[x + 1][y + 1] ? dp[x + 1][y + 1] : max;
			}
		}

		return max;
	}

	// Space O(m) or O(n) time O(mn)
	public int lccsDPLessSpace(char[] arr1, char[] arr2) {

		char[] s1, s2;
		if (arr1.length > arr2.length) {
			s1 = arr1;
			s2 = arr2;
		} else {
			s1 = arr2;
			s2 = arr1;
		}

		int[] dp = new int[s2.length + 1];

		int max = 0;
		for (int x = 0, size1 = s1.length; x < size1; ++x) {
			for (int y = s2.length - 1; y >= 0; --y) {
				if (s1[x] == s2[y]) {
					dp[y + 1] = dp[y] + 1;
				} else {
					dp[y + 1] = 0;
				}
				max = max < dp[y + 1] ? dp[y + 1] : max;
			}
		}

		return max;
	}

	public char[] lccsDPLessSpaceS(char[] arr1, char[] arr2) {

		char[] s1, s2;
		if (arr1.length > arr2.length) {
			s1 = arr1;
			s2 = arr2;
		} else {
			s1 = arr2;
			s2 = arr1;
		}

		char[] maxStr = null;
		int[] dp = new int[s2.length];

		int max = 0;
		for (int x = 0, size1 = s1.length; x < size1; ++x) {
			for (int y = s2.length - 1; y >= 0; --y) {
				if (s1[x] == s2[y]) {
					if (y == 0)
						dp[y] = 1;
					else
						dp[y] = dp[y - 1] + 1;
				} else {
					dp[y] = 0;
				}
				if (max < dp[y]) {
					max = dp[y];
					maxStr = Arrays.copyOfRange(s1, x - max + 1, x + 1);
				}
			}
		}

		return maxStr;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		LongestCommonConsecutiveSequence lccs = new LongestCommonConsecutiveSequence();
		char[] s1 = new String("FABABCDV").toCharArray();
		char[] s2 = new String("DEABABCDH").toCharArray();
		char[] maxStr = lccs.lccsDPLessSpaceS(s1, s2);
		System.out.printf("Result is %s with size %d (6)", new String(maxStr),
		        maxStr.length);
	}
}
